package com.wang.leetcode;

/**
 * @Author: along
 * @Create: 2021/4/26
 * @Description:有序的二维数组中的查找
 */
public class Sword04 {
    //在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
    //判断target是否存在该数组
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0) {
            return false;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        //定义数组中右上角的元素
        int row = 0;
        int col = columns - 1;
        while (row < rows && col >= 0) {
            int num = matrix[row][col];//右上角的元素
            if(target == num) {
                return true;
            }
            //大于num 说明target在num的下方 所以row++
            else if (target > num) {
                row++;
            }
            //小于num 说明target在num的左边 所以col--
            else {
                col--;
            }
        }
        return false;
    }
}
